Number of closed islands¶
Time: O(MxN); Space: O(1); medium
Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.
Return the number of closed islands.
Example 1:
Input: grid =
[
[1,1,1,1,1,1,1,0],
[1,0,0,0,0,1,1,0],
[1,0,1,0,1,1,1,0],
[1,0,0,0,0,1,0,1],
[1,1,1,1,1,1,1,0]
]
Output: 2
Explanation:
Islands in gray are closed because they are completely surrounded by water (group of 1s).
Example 2:
Input: grid =
[
[0,0,1,0,0],
[0,1,0,1,0],
[0,1,1,1,0]
]
Output: 1
Example 3:
Input: grid =
[
[1,1,1,1,1,1,1],
[1,0,0,0,0,0,1],
[1,0,1,1,1,0,1],
[1,0,1,0,1,0,1],
[1,0,1,1,1,0,1],
[1,0,0,0,0,0,1],
[1,1,1,1,1,1,1]
]
Output: 2
Constraints:
1 <= len(grid), len(grid[0]) <= 100
0 <= grid[i][j] <=1
Hints:
Exclude connected group of 0s on the corners because they are not closed island.
Return number of connected component of 0s on the grid.
[1]:
class Solution1(object):
"""
Time: O(M*N)
Space: O(1)
"""
def closedIsland(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
directions = [(0, 1),
(1, 0),
(0, -1),
(-1, 0)
]
def fill(grid, i, j):
if not (0 <= i < len(grid) and
0 <= j < len(grid[0]) and
grid[i][j] == 0):
return False
grid[i][j] = 1
for dx, dy in directions:
fill(grid, i + dx, j + dy)
return True
for j in range(len(grid[0])):
fill(grid, 0, j)
fill(grid, len(grid) - 1, j)
for i in range(1, len(grid)):
fill(grid, i, 0)
fill(grid, i, len(grid[0]) - 1)
result = 0
for i in range(1, len(grid) - 1):
for j in range(1, len(grid[0]) - 1):
if fill(grid, i, j):
result += 1
return result
[2]:
s = Solution1()
grid = [
[1,1,1,1,1,1,1,0],
[1,0,0,0,0,1,1,0],
[1,0,1,0,1,1,1,0],
[1,0,0,0,0,1,0,1],
[1,1,1,1,1,1,1,0]
]
assert s.closedIsland(grid) == 2
grid = [
[0,0,1,0,0],
[0,1,0,1,0],
[0,1,1,1,0]
]
assert s.closedIsland(grid) == 1
grid = [
[1,1,1,1,1,1,1],
[1,0,0,0,0,0,1],
[1,0,1,1,1,0,1],
[1,0,1,0,1,0,1],
[1,0,1,1,1,0,1],
[1,0,0,0,0,0,1],
[1,1,1,1,1,1,1]
]
assert s.closedIsland(grid) == 2